#!/usr/bin/env python

class DisjointSet:
    def __init__(self, vertices):
        self._parent = [-1] * vertices
        self._rank = [0] * vertices

    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 == root2:
            return False
        else:
            if self._rank[root1] > self._rank[root2]:
                self._parent[root2] = root1
            elif self._rank[root2] > self._rank[root1]:
                self._parent[root1] = root2
            else:
                self._parent[root1] = root2
                self._rank[root2] += 1
            return True

    def find(self, node):
        while self._parent[node] != -1:
            node = self._parent[node]
        
        return node

    def __str__(self):
        return str(self._parent)


if __name__ == "__main__":
    edges = [[0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

    disjoint_set = DisjointSet(6)
    for x, y in edges:
        if not disjoint_set.union(x, y):
            print(f'Cycle found! {x} -{y}')

    print(disjoint_set)
    